package algorithm.prim;

import java.util.Arrays;

public class PrimAlgorithm {
  public static void main(String[] args) {

    char[]data = new char[]{'A','B','C','D','E','F','G'};
    int verTex = data.length;
//    权值
    int[][] weight = new int[][]{
            {10000, 5, 7, 10000, 10000, 10000, 2},
            {5, 10000, 10000, 9, 10008, 10000, 3},
            {7, 10000, 10000, 10000, 8, 10000, 10000},
            {10000, 9, 10000, 10000, 10000, 4, 10000},
            {10000, 10000, 8, 10000, 10000, 5, 4},
            {10000, 10000, 10000, 4, 5, 10000, 6},
            {2, 3, 10000, 10000, 4, 6, 10000}
    };
    MGraph mGraph = new MGraph(verTex);
    MinTree minTree = new MinTree();
    minTree.createGraph(mGraph,verTex,data,weight);

//    显示图
    minTree.showGraph(mGraph);
//    测试
    minTree.prim(mGraph,0);
  }
}

class MinTree{

  public void createGraph(MGraph mGraph,int verTex,char[] data,int[][]weight){
    for (int i = 0; i < verTex; i++) {
      mGraph.data[i] = data[i];
      for (int j = 0; j < verTex; j++) {
        mGraph.weight[i][j] = weight[i][j];
      }
    }
  }
  public void showGraph(MGraph graph){
    for (int[] link : graph.weight) {
      System.out.println(Arrays.toString(link));
    }
  }
//  prim算法
  public void prim(MGraph graph,int v){
    int[] isVisited = new int[graph.verTex];

    isVisited[v] = 1;

    int h1 = -1;
    int h2 = -1;
    int minWeight = 10000;

    for (int k = 1; k < graph.verTex; k++) {//因为有 graph.verTex顶点，普利姆算法结束后，有graph.verTex-1边

//      这个是确定每一次生成的子图，和哪个结点的距离最近
      for (int i = 0; i < graph.verTex; i++) {//i结点表示被访问过的结点
        for (int j = 0; j < graph.verTex; j++) {//j结点表示还没被访问过的结点
          if (isVisited[i] == 1 && isVisited[j] == 0 && graph.weight[i][j] < minWeight){
            minWeight = graph.weight[i][j];
            h1 = i;
            h2 = j;
          }
        }
      }
      //找到一条边是最小
      System.out.println("边<" + graph.data[h1]+ "," + graph.data[h2]+"〉权值: " + minWeight);
      //将当前这个结点标记为已经访问
      isVisited[h2] = 1;
      //minweight重新设置为最大值10000
      minWeight = 10000;
    }

  }
}

class MGraph{

  int verTex;//表示图的节点数
  char data[];//存放数据
  int[][]weight;//表示图的边

  public MGraph(int verTex){
    this.verTex = verTex;
    data = new char[verTex];
    weight = new int[verTex][verTex];
  }

}